Software Defined Networking (SDN) is an approach to computer networking that employs a split architecture network in which the forwarding (data) plane is decoupled from the control plane. The use of a split architecture network simplifies the network devices (e.g., switches) implementing the forwarding plane by shifting the intelligence of the network into one or more controllers that oversee the switches. SDN facilitates rapid and open innovation at the network layer by providing a programmable network infrastructure. OpenFlow is a protocol that enables controllers and switches in an SDN network to communicate with each other. OpenFlow enables dynamic programming of flow control policies in the network.
A packet processing device such as a switch (e.g., OpenFlow switch) may include one or more packet processing tables (e.g., flow tables) that each include one or more rules (e.g., flow entries) for specifying how the switch should process incoming packets. Each rule may include one or more match fields that are used to match packets and one or more actions to apply to packets that match the rule.
A switch may use a lookup algorithm to match packets against rules in a packet processing table to find a matching rule. Currently, the OpenFlow standard does not specify the lookup algorithm that a switch should use to match packets against rules in a packet processing table. Most switches match packets using a hash-based lookup algorithm or a linear search lookup algorithm.
Sophisticated switches (e.g., OpenFlow switches) typically implement multiple diverse functionalities such as Media Access Control (MAC) learning, routing, and firewall functionality, with each of these functionalities implementing different packet processing tables containing different types of rules and different number of rules. Different types of lookup algorithms may have different lookup speeds when matching packets against rules in a packet processing table depending on the population of the packet processing tables. However, switches typically do not have a-priori information regarding the population of packet processing tables, and thus often resort to using a single generic lookup algorithm for all packet processing tables, which may result in suboptimal performance.